package leetcode;

import java.util.ArrayList;
import java.util.List;

//给定整数，返回所有可能的IP地址
//Given "25525511135",
//
//return ["255.255.11.135", "255.255.111.35"].
public class RestoreIPAddresses {

	public static void main(String[] args) {
		RestoreIPAddresses object = new RestoreIPAddresses();
		String ip = "010010";
		object.restoreIpAddresses(ip);
	}
	
	//最多有12个字符，放在4个篮子里面，每个篮子最少一个，最多三个。是一道组合题
	public List<String> restoreIpAddresses(String s) {
		List<String> res = new ArrayList<String>();
		if(s == null){
			return res;
		}
		int length = s.length();
		if(length < 4 || length > 12){
			return res;
		}
		List<String> temp = new ArrayList<>();
		backtrack(1, 0, length, s, res, temp);
		System.out.println(res);
		return res;
	}
	
	public void backtrack(int index, int start, int length, String s, List<String> res,
			List<String> temp){
		if(index == 4){
			//并且长度小于3，因为start是下标
			if(start < length && start + 3 >= length && Integer.parseInt(s.substring(start, length)) <= 255
					&& (start == length - 1 || s.charAt(start) != '0')){
				StringBuilder sb = new StringBuilder();
				for (String string : temp) {
					sb.append(string).append(".");
				}
				sb.append(s.substring(start, length));
				res.add(sb.toString());
			}
			return;
		}
		for (int i = 1; i <= 3; i++) {
//			if(start >= length){
//				break;
//			}
//			if(s.charAt(start) == '0'){
//		        temp.add(s.substring(start, start + 1));
//			    backtrack(index + 1, start + 1, length, s, res, temp);
//			    temp.remove(temp.size() - 1);
//			    break;
//		    }
			if(i + start > length){
				break;
			}
			//while I use this code runtime desc to 4ms from 5ms
			String sub = s.substring(start, start + i);
			if(sub.charAt(0) == '0' && sub.length() > 1){
				continue;
			}
			//除了不能大于255之外，还不能有前导0
			if(Integer.parseInt(sub) > 255){
				break;
			}
			temp.add(s.substring(start, start + i));
			backtrack(index + 1, start + i, length, s, res, temp);
			temp.remove(temp.size() - 1);
		}
	}
	
	//other's backtrack
	private void restoreIp(String ip, List<String> solutions, int idx, String restored, int count) {
	    if (count > 4) return;
	    if (count == 4 && idx == ip.length()) solutions.add(restored);
	    
		for (int i = 1; i < 4; i++) {
			if (idx + i > ip.length()){
				break;
			}
			//显然我可以在这一点上进行优化
			String s = ip.substring(idx, idx + i);
			if ((s.startsWith("0") && s.length() > 1)
					|| (i == 3 && Integer.parseInt(s) >= 256)){
				continue;
			}
			restoreIp(ip, solutions, idx + i, restored + s
					+ (count == 3 ? "" : "."), count + 1);
		}
	}
	
	
	//直接使用循环来做
	public List<String> restoreIpAddresses2(String s) {
		List<String> res = new ArrayList<String>();
		int len = s.length();
		for (int i = 1; i < 4 && i < len - 2; i++) {
			for (int j = i + 1; j < i + 4 && j < len - 1; j++) {
				for (int k = j + 1; k < j + 4 && k < len; k++) {
					String s1 = s.substring(0, i), s2 = s.substring(i, j), s3 = s
							.substring(j, k), s4 = s.substring(k, len);
					if (isValid(s1) && isValid(s2) && isValid(s3)
							&& isValid(s4)) {
						res.add(s1 + "." + s2 + "." + s3 + "." + s4);
					}
				}
			}
		}
		return res;
	}

	public boolean isValid(String s) {
		if (s.length() > 3 || s.length() == 0
				|| (s.charAt(0) == '0' && s.length() > 1)
				|| Integer.parseInt(s) > 255)
			return false;
		return true;
	}
}
